Exercise: Scapegoat Trees

Modify the add() method of the scapegoat tree.

We'll cover the following

Task#

Modify the add(x) method of the ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by the time the method wants to compute size(w), it has already computed one of size(w.left) or size(w.right).

Sample input

The sample input will be as follows:

5
3
8
1
4
7
9

Expected output

The expected output will be as follows:

Tree contents:
1 3 4 5 7 8 9 
Tree after removing 4:
1 3 5 7 8 9

Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.

Good luck!

svg viewer

Note: You must implement the method add() in the below code starting at line 57.

main.py
arrayqueue.py
binarytree.py
binarysearchtree.py
utils.py
base.py
Task to implement the add() method for ScapegoatTrees

Discussion on Scapegoat Trees

Solution: Scapegoat Trees